package Algorithm.StackAndQueue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author cj
 * @Date 2021/11/8 20:03
 */
public class getMaxWindow {

    public static int[] getMaxWindow1(int[] arr, int windowLen) {
        // 鲁棒性
        if (arr == null || windowLen < 1 || arr.length < windowLen) {
            return null;
        }
        Deque<Integer> qMax = new LinkedList<>();
        int[] res = new int[arr.length - windowLen + 1];
        for (int i = 0; i < arr.length; i++) {
            while (!qMax.isEmpty() && arr[i] > arr[qMax.getLast()]) {
                qMax.removeLast();
            }
            qMax.add(i);
            // 超出窗口范围
            if (qMax.getFirst() <= i - windowLen) {
                qMax.removeFirst();
            }
            if (i >= windowLen - 1) {
                res[i - windowLen + 1] = arr[qMax.getFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
        int[] res = getMaxWindow1(arr, 3);
        for (int a : res) {
            System.out.println(a);
        }
    }
 }
